package main

import "fmt"

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
// Related Topics 字符串 动态规划 回溯 👍 2363 👎 0
func main() {
	fmt.Println(generateParenthesis(1))
	fmt.Println(generateParenthesis2(1))
}

//leetcode submit region begin(Prohibit modification and deletion)
func generateParenthesis(n int) (ans []string) {
	var generateAll func(current []rune)
	generateAll = func(current []rune) {
		if len(current) == 2 * n  {
			if  isValid(string(current)) {
				ans = append(ans, string(current))
			}
			return
		}
		generateAll(append(current, '('))
		generateAll(append(current, ')'))
	}
	generateAll([]rune{})
	return
}



func isValid(current string) bool {
	var tmp int
	for _, letter := range current {
		if letter == '(' {
			tmp ++
		} else {
			tmp --
		}
		if tmp < 0 {
			return false
		}
	}
	if tmp != 0 {
		return false
	}
	return true
}

func generateParenthesis2(n int) (ans []string) {
	var generate func(str []rune, left, right int)
	generate = func(str []rune, left, right int) {
		if left == 0 && right == 0 {
			ans = append(ans, string(str))
			return
		}
		if left == right {
			generate(append(str, '('), left - 1, right)
		} else if left < right {
			if left > 0 {
				generate(append(str, '('), left - 1, right)
			}
			generate(append(str, ')'), left, right - 1)
		}
	}
	generate([]rune{}, n, n)
	return
}
//leetcode submit region end(Prohibit modification and deletion)

